/* sleep.c : sleep device (assignment 2)
 */

#include <kernel.h>

// Delta queue entry
// See http://everything2.com/title/delta+list
typedef struct _tag_delta_q {
	PCB* proc;
	uint metric;
	struct _tag_delta_q* next;
} DELTA_Q;

// The sleep queue
DELTA_Q* sleep_q = NULL;

// insert a proc into the delta queue
void delta_insert(PCB* proc, uint metric);

// output the sleep q, debugging
void dump_sleep_q();

// convert milliseconds to clock ticks 
uint ms_to_ticks(uint ms);


// sleep a process 
extern void sleep(PCB* proc, int ms){
	uint ticks;
	ticks = ms_to_ticks((uint)ms);
	
	//kprintf("Sleeping process %d for %d ticks...\n", proc->pid, ticks);

	delta_insert(proc, ticks);

}

// tick updates procs on the sleep q, ready()'s process done sleeping
extern void tick(){

	if(!sleep_q){
		return;
	}

	// decrement
	if(sleep_q->metric > 0){ 
		sleep_q->metric--;
	}

	if(sleep_q->metric == 0){
		// ready the process again		
		ready(sleep_q->proc);
		
		// remove it from the queue
		DELTA_Q* tmp;
		tmp = sleep_q;
		sleep_q = sleep_q->next;
		kfree(tmp);
		
	}
}


uint ms_to_ticks(uint ms){
	
	if(ms < CLOCK_TICK){
		return 1;
	}
	
	// ceiling
	return (ms / CLOCK_TICK) + (ms % CLOCK_TICK ? 1 : 0);
		
}

// insert a process in the delta (sleep) queue
void delta_insert(PCB* proc, uint metric){
	DELTA_Q *cur, *prv, *new;

	cur = sleep_q;
	prv = NULL;
	new = (DELTA_Q*)kmalloc(sizeof(DELTA_Q));
	
	/// XXX
	//dump_sleep_q();
	
	if(!new){
		kprintf("Couldn't allocate sleep queue entry.\n");
		return;
	}

	if(!proc){
		kprintf("Process to sleep was NULL.\n");
		return;
	}
	
	new->proc = proc; 
	
	// queue is empty
	if(!cur){
		new->metric = metric;
		new->next = NULL;
		sleep_q = new;
		
		/// XXX
		//dump_sleep_q();
		return;
	}
	
	// otherwise, update delta list
	while(cur){
		if(cur->metric < metric){
			metric -= cur->metric;
		}else{
			// insert
			if(prv){
				// in the middle
				prv->next = new;
				new->next = cur;
				new->metric =  metric;
				cur->metric -= metric;
				return;		
			}else{
				// at the head
				new->next = cur;
				new->metric = metric;
				cur->metric -= metric;
				sleep_q = new;
				return;
			}	
		}

		// iterate
		prv = cur;
		cur = cur->next;
	}

	// at the end
	new->next = NULL;
	new->metric = metric;
	prv->next = new;
	
	/// XXX
	//dump_sleep_q();

}

void dump_sleep_q(){
	kprintf("Sleep Queue: ");
	
	if(!sleep_q){
		kprintf("empty.\n");
		return;
	}
	
	DELTA_Q* cur;
	cur = sleep_q;
	while(cur){
		kprintf("%d (%d)", cur->proc->pid, cur->metric);
		if(cur->next != NULL)
			kprintf(" -> ");
		cur = cur->next;
	}
	kprintf("\n");
}

